1. Field of the Invention
Embodiments of the present invention relate to the field of digital communication systems. More specifically, embodiments of the present invention relate to implementing interleavers and de-interleavers in a memory efficient manner.
2. Related Art
Frequently data that is transmitted over a channel from one electronic device (transmitting device) to another electronic device (receiving device) is corrupted, for example, due to channel impairments, such as noise, fading and jamming. Various methods, such as forward error correction (FEC), have been developed to correct the errors in the data at the receiving device (a classical example of FEC is the Reed-Solomon encoder/decoder). In one approach, FEC uses error free data around the bad data to correct the bad data. For example, the transmitting device may transmit a data stream of symbols “A B C D E F G H I J K L” to a receiving device. For the purposes of illustration, data shall be represented herein with symbols, such as “A,” “B,” “C,” etc.
Errors, represented by “X”s, may be interjected into the data stream so that the receiving device receives a data stream of symbols “A X C D E X G H I X K L.” Forward error correction may use good data, as represented by symbols “A,” “C D E,” “G H I,” “K L,” that is around the bad data to correct the bad data. However, if a sufficient number of errors occur within a relatively short period of time, there may not be enough good data around the bad data to correct the bad data. For example, if a device receives a data stream, such as “A B C X X X G H I J K L,” where several symbols which are received in a short time span are in error, then there may not be enough good data in between the bad data to correct the bad data.
One approach to spreading out the errors in a data stream of symbols involves rearranging the order that the symbols are transmitted and received using interleavers. FIG. 1 is a block diagram of a system with electronic devices that use two interleavers. A system 100 as depicted in FIG. 1 can be used in one way communications such as the communication from a DVD player to a television, a satellite to a moon rover, etc. As depicted in FIG. 1, an electronic transmitting device 110 transmits symbol sets to an electronic receiving device 120 over a transmission channel 130. Electronic transmitting device 110 includes a source 112 that symbol sets are read from and electronic receiving device 120 includes a sink 122 for using the symbol sets that are received from electronic receiving device 110. Both electronic devices 110, 120 each include two interleavers 114, 116, 124, 126, as will be explained in more detail.
Interleavers exist in several types. One type is the block interleaver. The block interleaver consists of a square or a rectangular array of memory. Data, such as that represented by symbols, may be written to this memory array in row order and read from this memory array in column order, for example. In this way, consecutive symbols are distributed over time when transmitted. This process is performed prior to transmission of the data and a complementary process is performed after reception of the data. For example, in the event that electronic transmitting device 110 retrieves data stream of symbols “A B C D E F G H I J K L” (referred to herein as a “symbol set”) from source 112, the data stream of symbols “A B C D E F G H I J K L” may be written to interleaver 114 in row order as depicted in Table 1 below:
TABLE 1data written to interleaver 114 in row orderABCDEFGHIJKLHowever, the data is read from interleaver 114 in column order (e.g., “A E I B F J C G K D H L”), thereby interleaving the symbols, and transmitted to electronic receiving device 120 over transmission channel 130 where transmission errors may result in corruption of consecutive symbols associated with the data stream. A symbol set includes the number of symbols that an interleaver can hold, such as that depicted in Table 1 for example.
Electronic receiving device 120 receives data from electronic transmitting device 110 and de-interleaves the symbols in the opposite order. For example, the data stream of symbols “A E I B F J C G K D H L” is written to interleaver 124 in column order as depicted in Table 2 below.
TABLE 2data stream stored in interleaver 124 in column orderABCDEFGHIJKLThe data is read out of interleaver 124 in row order to obtain the data stream of symbols “A B C D E F G H I J K L” and written to sink 122. Interleavers 124, 126 are also known as “de-interleavers.”
The nature of systems using block interleavers requires that no data be read from an interleaver until a full block of data has been written to an interleaver (e.g., the block interleaver is full). In a real-time system, symbols must continuously be written and read from the block interleaver concurrently. As a result, it is necessary to employ two interleavers (e.g., one for reading and one for writing and their roles ping-pong). This dual interleaver requirement exists in both the transmitting device and the receiving device. System 100 depicts this dual interleaver requirement. For example, electronic transmitting device 110 depicts interleaver 114 and interleaver 116. Similarly, electronic receiving device 120 depicts interleaver 124 and interleaver 126. Interleavers 114, 116, 124, 126 provide similar functionality, except that interleavers 114 and 116 are associated with electronic transmitting device 110 and interleavers 124 and 126 are associated with electronic receiving device 120.
When all of the symbols have been read from a particular interleaver, the roles of the interleavers are swapped. For example, as symbols are being read from one interleaver 114 associated with a device 110, other symbols are being written to the other interleaver 116 associated with the device 110. When all of the symbols associated with one of the interleavers 114 have been read, the interleavers 114, 116 are swapped (also referred to herein as “ping-pong”), thus, after swapping the interleavers, symbols are written to interleaver 114 and symbols are read from interleaver 116.
Memory is expensive and a considerable amount of memory is needed for implementing interleavers in real-time systems, such as video systems. Therefore, there is a need for efficiently using memory for implementing interleavers.